Section: Scientific Foundations

Constraint Solving Techniques

Constraint propagation algorithms use constraints actively during search for filtering the domains of variables. These domain reductions are the only way constraints communicate. Our research concerns different constraint domains, namely:

• finite domains (bounded natural numbers): membership, arithmetic, reified, higher order and global constraints;

• reals: polyhedral libraries for linear constraints and interval methods;

• terms: subtyping constraints;

• graphs: subgraph epimorphism (SEPI) and isomorphism constraints; acyclicity constraint;

• Kripke structures: temporal logic constraints (quantifier-free first order CTL constraints).

We develop new constraints and domain filtering algorithms by using already existing constraint solving algorithms and implementations. For instance, we use the Parma Polyhedra Library PPL with its interface with Prolog for solving temporal logic constraints over the reals. Similarly, we use standard finite domain constraints for developing solvers for the new SEPI constraint.